package com.jxm.sort;

import java.util.Arrays;

/**
 * @Author: jxm
 * @Description: 插入排序api设计
 * @Date: 2022/6/9 10:23
 * @Version: 1.0
 */
public class Insertion {

    /**
     * 原理：
     * 1.把所有的元素分为两组，已经排序的和未排序的；
     * 2.找到未排序的组中的第一个元素，向已经排序的组中进行插入；
     * 3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待
     * 插入元素放到这个位置，其他的元素向后移动一位；
     */

    /**
     * 对数组a元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        for(int i = 1;i<a.length;i++){ //待排序元素
            for (int j=i;j>0;j--){
                //比较索引j处的值和索引j-1索引处的值，如果索引j-1处的值比j处的值大，则交换数据，那么就找到合适的位置了，退出循环即可；
                if(greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else{
                    break; //退出内层循环
                }
            }

        }
    }

    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w) > 0;
    }

    /**
     * 数据元素 i 和 j 交换位置
     */
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //最坏情况下：时间复杂度为O(N^2);
    public static void main(String[] args) {
        Integer[] array = {4,3,2,10,12,1,5,6};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

}
